/**
 * 3.7 查找算法
静态查找表之有序表的查找
1. 实现二分查找（迭代版）：在升序数组中查找 x，返回索引（无则返回 - 1）。
测试用例：[1,3,5,7,9]，查找 5 返回 2，查找 4 返回 - 1。
2. 基于二分查找实现 "插入位置确定"：在升序数组中找到 x 应插入的位置（保证插入后仍有序）。
测试用例：[1,3,5]，x=2→插入位置 1；x=6→插入位置 3。
静态查找表之顺序表的查找
1. 实现顺序查找（含哨兵优化）：在无序数组中查找值 x，返回第一个匹配索引（无则返回 - 1）。
测试用例：数组 [3,1,4,1,5]，查找 1 返回 1，查找 6 返回 - 1。
2. 设计 "频率统计" 函数：用顺序查找统计数组中每个元素出现的次数，返回频率最高的元素（若有多个返回第一个）。
测试用例：[2,3,2,5,2,3]→频率最高为 2（3 次）。
 */

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

// 1. 二分查找（迭代版）
int binarySearch(int arr[], int n, int x) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 避免溢出
        if (arr[mid] == x) return mid;
        else if (arr[mid] < x) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// 2. 插入位置确定（基于二分查找）
int searchInsert(int arr[], int n, int x) {
    int left = 0, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < x) left = mid + 1;
        else right = mid;
    }
    return left;
}

// 3. 顺序查找（含哨兵优化）
int sequentialSearch(int arr[], int n, int x) {
    if (n == 0) return -1;
    // 哨兵放在数组末尾
    if (arr[n-1] == x) return n-1;
    int temp = arr[n-1];
    arr[n-1] = x; // 设置哨兵
    
    int i = 0;
    while (arr[i] != x) i++;
    
    arr[n-1] = temp; // 恢复原数据
    return (i == n-1) ? -1 : i;
}

// 4. 频率统计（返回频率最高的元素，若有多个返回第一个）
int maxFrequencyElement(int arr[], int n) {
    if (n == 0) return -1; // 空数组处理
    int maxCount = 0;
    int result = arr[0];
    
    for (int i = 0; i < n; i++) {
        int count = 0;
        // 顺序查找当前元素出现次数
        for (int j = 0; j < n; j++) {
            if (arr[j] == arr[i]) count++;
        }
        // 更新最大频率（仅当次数更多时更新，保证第一个出现的）
        if (count > maxCount) {
            maxCount = count;
            result = arr[i];
        }
    }
    return result;
}
//
// 查找算法测试
void testSearch() {
    // 二分查找测试
    int arr1[] = {1,3,5,7,9};
    printf("二分查找 5: %d（预期2）\n", binarySearch(arr1, 5, 5));
    printf("二分查找 4: %d（预期-1）\n", binarySearch(arr1, 5, 4));
    
    // 插入位置测试
    int arr2[] = {1,3,5};
    printf("插入2的位置: %d（预期1）\n", searchInsert(arr2, 3, 2));
    printf("插入6的位置: %d（预期3）\n", searchInsert(arr2, 3, 6));
    
    // 顺序查找测试
    int arr3[] = {3,1,4,1,5};
    printf("顺序查找1: %d（预期1）\n", sequentialSearch(arr3, 5, 1));
    printf("顺序查找6: %d（预期-1）\n", sequentialSearch(arr3, 5, 6));
    
    // 频率统计测试
    int arr4[] = {2,3,2,5,2,3};
    printf("频率最高元素: %d（预期2）\n", maxFrequencyElement(arr4, 6));
}